import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Iterator;


public class ComplexityAlgorithm {
	
	public static void main(String[] args){
		Expression e = new Expression();
		int a = e.exp4(3, 4);
		System.out.println(a);
//		e.towerHaNoi(3, "disk 0", "disk 1", "disk 2");
		int[] arr = {3,5,1,6,2};
		e.InsertionSort(arr);
		System.out.println(Arrays.toString(arr));
	}
	
}

class Expression{
	/**
	 * Time: 2 + 3b (2: ass + return, 3: loop 3 times)
	 * @param a
	 * @param b
	 * @return
	 */
	public int exp1(int a, int b){
		int ans = 1;
		while (b > 0) {
			ans *= a;
			b--;
		}
		return ans;
	}
	
	/**
	 * Time : 3 + t(b-1) => 3 + 3 + t(b - 2) => 3 + 3 + 3 + t(b-3) => 3*k + t(b-k)
	 * Stop: b - k = 1 => k = b - 1
	 * 3*(b-1) + t(1) => 3b - 1
	 * @param a
	 * @param b
	 * @return
	 */
	public int exp2(int a, int b){
		if (b == 1) {
			return a;
		} else {
			return a * exp2(a, b - 1);
		}
	}
	
	/**
	 * b even: t(b)= 5 + t(b/2)
	 * b old : t(b)= 5 + t(b-1) = 5 + 5 + t((b-1)/2) = 5 + 5 + t(b/2) = 5 + 5 + 5 + t(b/(2^2))
	 *  = 5*k + t(b/(2^k))
	 *  Stop : b/(2^k) = 1 => b = 2^k => k = log2 b
	 *  O(log2 b)
	 * @param a
	 * @param b
	 * @return
	 */
	public int exp3(int a, int b){
		if(b == 1){
			return a;
		}
		if (b%2 == 0) {
			return exp3(a*a, b/2);
		} else {
			return a*exp3(a, b-1);
		}
	}
	
	/**
	 * Time  = a*b
	 * @param a
	 * @param b
	 * @return
	 */
	public int exp4(int a, int b){
		int k = 0;
		for (int i = 0; i < a; i++) {
			for (int j = 0; j < b; j++) {
				k += 1;
			}
		}
		return k;
	}
	
	/**
	 * 2^n
	 * @param size
	 * @param fromPole
	 * @param toPole
	 * @param spacePole
	 */
	public void towerHaNoi(int size, String fromPole, String toPole, String spacePole){
		if (size == 1) {
			System.out.println("Move disk from " + fromPole + " to " + toPole);
		} else {
			towerHaNoi(size - 1, fromPole, spacePole, toPole);
			towerHaNoi(1, fromPole, toPole, spacePole);
			towerHaNoi(size - 1, spacePole, toPole, fromPole);
		}
	}
	
	public void InsertionSort(int[] arr){
		int key, j;
		for (int i = 0; i < arr.length; i++) {
			key = arr[i];
			j = i;
			while( (j>0) && (arr[j-1] > key)){
				arr[j] = arr[j-1];
				j--;
			}
			arr[j] = key;
		}
	}
	
}


